import time


# 辗转相除法求最大公约数
def gcd(a, b):
    return gcd(b, a % b) if b > 0 else a


# 更相减损法求最大公约数
def gcd_msm(a, b):
    if a == b:
        return a
    reduction = 1
    while True:
        if a % 2 == 0 and b % 2 == 0:
            a //= 2
            b //= 2
            reduction *= 2
        else:
            break
    while True:
        minNum = min(a, b)
        maxNum = max(a, b)
        if minNum * 2 == maxNum:
            return minNum * reduction
        else:
            a = minNum
            b = maxNum - minNum


# 求最小公倍数
def lcm(a, b):
    return a * b / gcd(a, b)


x = 501
y = 50000

start = time.perf_counter()
print(gcd(b=x, a=y))
end = time.perf_counter()
print(end - start)
start = time.perf_counter()
print(gcd_msm(x, y))
end = time.perf_counter()
print(end - start)
print(lcm(x, y))
